package two.chapter_4.c4_2;

import two.chapter_1.c1_3.LinkStack;
import two.chapter_1.c1_3.Stack;

/**
 * 寻找有向图中的有向环
 */
public class DirectedCycle {

    private boolean []marked;
    private int [] edgeTo;
    private Stack<Integer> cycle;
    private boolean[] onStack;
    public DirectedCycle(Digragh g){
        onStack=new boolean[g.v()];
        edgeTo=new int[g.v()];
        marked=new boolean[g.v()];
        for (int v=0;v<g.v();v++){
            if (!marked[v]){
                dfs(g,v);
            }
        }
    }

    private void dfs(Digragh g, int v) {
        marked[v]=true;
        onStack[v]=true;
        for (int w:g.adj(v)){
            if (this.hasCycle()) return;
            else if (!marked[w]){
                edgeTo[w]=v;
                dfs(g,w);
            }else if (onStack[w]){
               cycle=new LinkStack<>();
               for (int x=v;x!=w;x=edgeTo[x]){
                   cycle.push(x);
               }
               cycle.push(w);
               cycle.push(v);
            }
        }
        onStack[v]=false;
    }

    /**
     * g中是否含有有向环
     * @return
     */
    public boolean hasCycle(){
        return cycle!=null;
    }

    /**
     * 。有向环中的所有顶点
     * @return
     */
    Iterable<Integer> cycle(){
        return cycle;
    }
}
